//
// Created by Administrator on 2021/8/24.
//
//一个国家有 n个城市，城市编号为0到n - 1，题目保证 所有城市都由双向道路 连接在一起。
// 道路由二维整数数组edges表示，其中edges[i] = [xi, yi, timei]表示城市xi 和yi之间有一条双向道路，耗费时间为timei分钟。
// 两个城市之间可能会有多条耗费时间不同的道路，但是不会有道路两头连接着同一座城市。
//
//每次经过一个城市时，你需要付通行费。通行费用一个长度为 n且下标从 0开始的整数数组passingFees表示，
// 其中passingFees[j]是你经过城市 j需要支付的费用。
//
//一开始，你在城市0，你想要在 maxTime分钟以内（包含 maxTime分钟）到达城市n - 1。
// 旅行的 费用 为你经过的所有城市 通行费之和（包括起点和终点城市的通行费）。
//
//给你maxTime，edges和passingFees，请你返回完成旅行的最小费用，如果无法在maxTime分钟以内完成旅行，请你返回-1。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/minimum-cost-to-reach-destination-in-time
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


// 和787差不多
// 787 是按步数计算  这里是按时间计算
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    int minCost(int maxTime, vector<vector<int>> &edges, vector<int> &passingFees) {
        /**
         * dp[t][j] :恰好使用了t的时间到达j的最小花费
         * dp[t][j] = dp[t-cost[i][j]][i] + passingFees[j]
         * (i,j)是一条通路
         */
        static constexpr int INF = 1000 * 1000 + 1;
        int n = (int) passingFees.size();
        vector<vector<int>> dp(maxTime + 1, vector<int>(n, INF));
        dp[0][0] = passingFees[0];
        for (int t = 1; t <= maxTime; ++t) {
            for (auto &edge:edges) {
                int from = edge[0], to = edge[1], cost = edge[2];
                if (cost <= t) {
                    // 道路是双向的
                    dp[t][to] = min(dp[t][to], dp[t - cost][from] + passingFees[to]);
                    dp[t][from] = min(dp[t][from], dp[t - cost][to] + passingFees[from]);
                }
            }
        }
        int ans = INF;
        for (int i = 1; i <= maxTime; ++i) {
            ans = min(ans, dp[i][n - 1]);
        }
        return ans == INF ? -1 : ans;
    }
};

int main() {
    vector<vector<int>> edges{{0, 1, 10},
                              {1, 2, 10},
                              {2, 5, 10},
                              {0, 3, 1},
                              {3, 4, 10},
                              {4, 5, 15}};
    vector<int> passingFees{5, 1, 2, 20, 20, 3};
    Solution solution;
    cout << solution.minCost(30, edges, passingFees) << endl;
    return 0;
}
